package jutf8search;

import java.io.Serializable;
import java.util.Vector;
/**
 * The Boyer-Moore algorithm, implemented using the jutf8search.Search interface.
 * 
 */
@SuppressWarnings("serial")
public class BM implements ExactSearchInterface, Serializable
{
    private int[]  b; // bad character shift list
    private int[]  f; // f[i] = widest border of suffix of the pattern at i
    private int[]  s; // good suffix list
    private int    m; // pattern size
    private byte[] query;
    private long   match;

    /* 
     * Boyer-Moore match number algorithm, returns position of the matchNum match
     */
    public long matchNum(byte[] text, long matchNum)
    {
        int i=0, j;
        int unsignedByte = 0;
        while(i<=text.length-m)
        {
            j=m-1;
            // test each character between pattern and text
            while(j>=0 && query[j]==text[i+j]) j--;
            // if full match
            if(j<0)
            {
                match++;
                if(match==matchNum) return i;
                i+=m;
            }
            // otherwise move on
            else
            {
            	unsignedByte = text[i+j] & 0xFF;
            	i+= Math.max(s[j+1],b[unsignedByte]);
            }
        }
        return -1;
    }

    /* 
     * Boyer-Moore match number algorithm, returns position of the matchNum match
     */
    public long numMatches(byte[] text)
    {
        int i=0, j;
        int unsignedByte = 0;
        long numMatches = 0;
        while(i<=text.length-m)
        {
            j=m-1;
            // test each character between pattern and text
            while(j>=0 && query[j]==text[i+j]) j--;
            // if full match
            if(j<0)
            {
                numMatches++;
                i+=s[0];
            }
            // otherwise move on
            else
            {
            	unsignedByte = text[i+j] & 0xFF;
            	i+= Math.max(s[j+1],b[unsignedByte]);
            }
        }
        return numMatches;
    }

    /* 
     * Boyer-Moore algorithm, returns all match positons in text
     */
    public Vector<Long> fullSearch(byte[] text)
    {
        int i=0, j;
        int unsignedByte = 0;
        Vector<Long> results = new Vector<Long>();
        while(i<=text.length-m)
        {
            j=m-1;
            // test each character between pattern and text
            while(j>=0 && query[j]==text[i+j]) j--;
            // if full match
            if(j<0)
            {
                results.add(new Long(i));
                i+=s[0];
            }
            // otherwise move on
            else
            {
            	unsignedByte = text[i+j] & 0xFF;
            	i+= Math.max(s[j+1],b[unsignedByte]);
            }
        }
        return results;
    }

    /* build table with string query */
	public void buildTable(String query)
    {
		buildTable(Utilities.getBytes(query));
	}

    /* build table with byte array query */
	public void buildTable(byte[] query)
    {
        b = new int[ExactSearch.ALPHABET_SIZE];
        m = query.length;
        f = new int[m+1];
        s = new int[m+1];
        this.query = query;
        computeBadCharShift();
        computeGoodSuffix1();
        computeGoodSuffix2();
	}

    /* compute where the matching suffix occurs in the pattern */
    private void computeGoodSuffix1()
    {
        int i=m;
        int j=m+1;
        f[i] = j;
        while(i > 0)
        {
            while(j<=m && query[i-1] != query[j-1])
            {
                if(s[j]==0) s[j]=j-i;
                j=f[j];
            }
            i--;
            j--;
            f[i]=j;
        }
    }

    /* compute where only part of the matching suffix occus at the 
       beginning of the pattern */
    private void computeGoodSuffix2()
    {
        int j = f[0];
        for(int i=0; i<=m; i++)
        {
            if(s[i]==0) s[i] = j;
            if(i==j) j = f[j];
        }
    }

    /* right most ocurrence of each character in alphabet, -1 if 
       not in alphabet */
    private void computeBadCharShift()
    {
        int unsignedByte = 0;
        b = new int[ExactSearch.ALPHABET_SIZE];
        for(int i=0; i<ExactSearch.ALPHABET_SIZE; i++) b[i] = m;
        for(int i=0; i<query.length-1; i++)
        {
            unsignedByte = query[i] & 0xFF;
            b[unsignedByte] = m - 1 - i;
        }
    }

    public void printArray(int[] a)
    {
        for(int i=0; i<a.length; i++) System.out.println("["+i+"] "+a[i]);
    }

    /* main method to test */
    public static void main(String[] args)
    {
        BM program = new BM();
        program.buildTable(args[0]);
        for(int i=0; i<program.s.length; i++)
        {
            System.out.println(i+": "+program.s[i]);
        }
    }

	public int getPatternSize() {
		return m;
	}

	public void resetMatch() {
		match = 0;
	}
}
